package LeetCode.leetcode113;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (root == null)
            return res;
        backTracking(path, res, root, targetSum);
        return res;
    }

    public static void backTracking(List<Integer> path, List<List<Integer>> res, TreeNode curNode, int target) {
        path.add(curNode.val);
        //推出条件
        if (curNode.left == null && curNode.right == null) {
            if (target - curNode.val == 0) {
                //找到一个符合的路径
                res.add(new ArrayList<>(path));
            }
            return;
        }

        if (curNode.left != null) {
            target -= curNode.val;
            backTracking(path, res, curNode.left, target);
            target += curNode.val;
            path.remove(path.size() - 1);
        }
        if (curNode.right != null) {
            target -= curNode.val;
            backTracking(path, res, curNode.right, target);
            target += curNode.val;
            path.remove(path.size() - 1);
        }
    }

    //    public static void backTracking(List<Integer> path, List<List<Integer>> res, TreeNode curNode, int size, int target) {
//        //推出条件
//        if (curNode.left == null && curNode.right == null) {
//            if (target == 0) {
//                //找到一个符合的路径
//                path.add(curNode.val);
//                res.add(new ArrayList<>(path));
//                path.remove(path.size()-1);
//            }
//            return;
//        }
//        for (int i = 0; i < size; i++) {
//            if (curNode.left != null) {
//                int count = 0;
//                if (curNode.left.left != null) {
//                    count += 1;
//                }
//                if (curNode.left.right != null) {
//                    count += 1;
//                }
//                path.add(curNode.val);
//                target -= curNode.left.val;
//                backTracking(path, res, curNode.left, count, target);
//                target += curNode.val;
//                path.remove(path.size() - 1);
//            }
//            if (curNode.right != null) {
//                int count = 0;
//                if (curNode.right.left != null) {
//                    count += 1;
//                }
//                if (curNode.right.right != null) {
//                    count += 1;
//                }
//                path.add(curNode.val);
//                target -= curNode.right.val;
//                backTracking(path, res, curNode.right, count, target);
//                target += curNode.val;
//                path.remove(path.size() - 1);
//            }
//        }
//    }


}
